Search for: All records

QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore as a quantum counterpart of AC0, along with the conjecture that QAC0 circuits cannot compute PARITY. In this work, we make progress on this long-standing conjecture: we show that any depth-𝑑 QAC0 circuit requires 𝑛^{1+3^{−𝑑}} ancillae to compute a function with approximate degree Θ(𝑛), which includes PARITY, MAJORITY and MOD_𝑘. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first lower bound on the super-linear sized QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to 𝑛^{1+exp(−𝑜(𝑑))} would imply that PARITY ∉ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0 circuits. We show that a depth-𝑑 QAC0 circuit with 𝑎 ancillae, when applied to low-degree operators, has a degree (𝑛 + 𝑎)^{1−3^{−𝑑}} polynomial approximation in the spectral norm. This implies that the class QLC0, corresponding to linear size QAC0 circuits, has an approximate degree 𝑜(𝑛). This is a quantum generalization of the result that LC0 circuits have an approximate degree 𝑜(𝑛) by Bun, Kothari, and Thaler. Our result also implies that QLC0 ≠ NC1.